
class Solution {
    public int profitableSchemes(int n, int m, int[] group, int[] profit) {
        int mod = (int)(10e9 + 7);
        int len = group.length;
        int[][][] dp = new int[len+1][n+1][m+1];
        for(int i = 0; i<= n; i++) {
            dp[0][i][0] = 1;
        }
        for(int i = 1; i<=len; i++) {
            for(int j = 0; j <= n; j++) {
                for(int k = 0; k <= m; k++) {
                    dp[i][j][k] = dp[i-1][j][k];
                    dp[i][j][k] %= mod;
                    if(j >= group[i-1]) {
                        dp[i][j][k] += dp[i-1][j-group[i-1]][Math.max(0,k-profit[i-1])];
                    }
                    dp[i][j][k] %= mod;
                }
            }
        }

        return dp[len][n][m];
    }
}

public class Test {
}
